/* Kruskal.java */
import graph.*;
import set.*;
import list.*;
import mergesort.*;
import dict.*;

/**
 * The Kruskal class contains the method minSpanTree(), which implements
 * Kruskal's algorithm for computing a minimum spanning tree of a graph.
 */

public class Kruskal {
	/**
	 * minSpanTree() returns a WUGraph that represents the minimum spanning tree
	 * of the WUGraph g.  The original WUGraph g is NOT changed.
	 */
	public static WUGraph minSpanTree(WUGraph g) {
		WUGraph T = new WUGraph();
		initializeVertices(T, g);
		LinkedQueue edgeAndWeights = listifyEdges(g);
		MergeSort.mergeSort(edgeAndWeights);
		buildTree(edgeAndWeights, T);
		return T;
	}

	/**
	 * initializeVertices() completes step [1] in Kruskal's algorithm: it gets the 
	 * list of the vertices in the oldGraph and adds it to the newGraph.  Note that 
	 * edges are NOT added to newGraph.
	 * @param newGraph is the graph to which vertices from oldGraph will be added to
	 * @param oldGraph is the graph which already contains vertices (and edges)
	 * 
	 * Runtime:  O(|V|), since getVertices() is in O(|V|) and addVertex (called |V| times)
	 * is in O(1).
	 */
	private static void initializeVertices(WUGraph newGraph, WUGraph oldGraph) {
		Object[] vertexList = oldGraph.getVertices();
		for (Object v : vertexList) {
			newGraph.addVertex(v);
		}
	}

	/**
	 * listifyEdges() completes step [2] in Kruskal's algorithm: it takes a graph g 
	 * and returns a list of all of the edges in g.
	 * WARNING:  This list is NOT sorted!
	 * @param g is the input graph
	 * @return unsorted list of all edges in g
	 * 
	 * Runtime:  O(|V| + |E|) - getVertices() is in O(|V|); getNeighbors() runs in O(d) 
	 * but it is run |V| times, so it is in O(|E|).  toEdgeList() will be in O(|E|) 
	 * because it adds together all of the edges.  concatList() runs in O(1).
	 */
	private static LinkedQueue listifyEdges(WUGraph g) {
		Object[] vertexList = g.getVertices();
		LinkedQueue edgeList = new LinkedQueue();	// List of edges is initially empty.
		LinkedQueue nList;
		for (Object v : vertexList) {
			Neighbors neighbors = g.getNeighbors(v);
			if (neighbors != null) {
				nList = toEdgeList(v, neighbors);
				edgeList = concatList(edgeList, nList);
			}
		}
		return edgeList;
	}

	/**
	 * toEdgeList() takes a Neighbors object and converts its representation to a  
	 * linked queue.
	 * This is a helper function for listifyEdges().
	 * @param v is the current vertex whose Neighbors are being constructed.
	 * @param n is the input Neighbors object.
	 * @return list of the edges in preparation for concatenation.
	 * 
	 * Runtime:  O(|E|)
	 */
	private static LinkedQueue toEdgeList(Object v, Neighbors n) {
		if (n == null || (n.neighborList.length != n.weightList.length)) {
			return null; 
		}
		LinkedQueue myEdgeList = new LinkedQueue();
		for (int i = 0; i < n.neighborList.length; i++) {	// neighborList.length should equal weightList.length
			myEdgeList.enqueue(new EdgeAndWeight(v, n.neighborList[i], n.weightList[i]));
		}
		return myEdgeList;
	}

	/**
	 * concatList() takes two LinkedQueue lists and concatenates them into a 
	 * single list.
	 * This is a helper function for listifyEdges().
	 * @param l1 is the first list to be concatenated
	 * @param l2 is the second list to be concatenated
	 * @return a list containing both l1 and l2
	 * 
	 * Runtime:  O(1)
	 */
	private static LinkedQueue concatList(LinkedQueue l1, LinkedQueue l2) {
		l1.append(l2);
		return l1;
	}

	/**
	 * buildTree() completes step [4] in Kruskal's Algorithm; it uses sets to 
	 * determine which edges to add to the new graph.  Edges are added only if 
	 * no existing path currently exists; in other words, they are added if the 
	 * two vertices are in different sets.
	 * @param edges is a list of all of the edges in the graph
	 * @param T is the which we will be adding vertices to
	 * 
	 * Runtime:  O(|V| + |E| log |E|)
	 */
	private static void buildTree(LinkedQueue edges, WUGraph T) {
		Object[] vertexList = T.getVertices();
		Dictionary mapVertices = buildDictionary(vertexList);
		DisjointSets mySet = new DisjointSets(vertexList.length);	// vertexList.length is number of vertices in graph.

		while (!edges.isEmpty()) {
			try {
				EdgeAndWeight curr = (EdgeAndWeight)(edges.dequeue());
				int currOrigin = (Integer)(mapVertices.find(curr.origin()).value());	// Corresponding int to the origin and dest respectively.
				int currDest = (Integer)(mapVertices.find(curr.dest()).value());
				int currWeight = curr.weight();

				currOrigin = mySet.find(currOrigin);
				currDest = mySet.find(currDest);

				if (currOrigin != currDest) {
					T.addEdge(curr.origin(), curr.dest(), currWeight);
					mySet.union(currOrigin, currDest);
				}

			} catch (QueueEmptyException e) {
				System.err.println(e);
			}
		}
	}

	/**
	 * buildDictionary() takes a list of vertices and associates them to unique 
	 * integers, as mapped by the dictionary.
	 * This is a helper function for buildTree().
	 * @param vertexList is a list of vertices in the graph
	 * @return a dictionary mapping a vertex to its corresponding unique integer.
	 * 
	 * Runtime:  O(|V|)
	 */
	private static Dictionary buildDictionary(Object[] vertexList) {
		Dictionary dict = new HashTableChained();
		for (int i = 0; i < vertexList.length; i++) {
			dict.insert(vertexList[i], i);	// Associate vertex with its position in array (which must be unique).
		}
		return dict;
	}

	/**
	 * verify() is a helper function used for testing purposes only.  It 
	 * prints an error message whenever a test fails.
	 * @param invariant
	 * @param message
	 * @author Jonathan Eng
	 */
	public static void verify (boolean invariant, String message) {
		if (!invariant) {
			System.out.println("*** ERROR: " + message);
			Thread.dumpStack();
		}
		else {
			System.out.println("Test passed.");
		}
	}

	/**
	 * Testing purposes only.
	 * @param args
	 */
	public static void main (String[] args) {
		Kruskal k = new Kruskal();
		boolean t;

		/* Graph g1.	
		     +-+                                                           
		     |5|                                                           
		     +-+                                                           
		     /   \                                                         
		(3) /     \ (5)                                                        
		   /       \                                                      
		 +-+       +-+                                                   
		 |1|-------|4|                                                   
		 +-+  (3)  +-+                                                  
		  | \                                                               
		  |  \                                                             
	   (1)|   \ (2)                                                        
		  |    \
		  |     \
		  +-+     +-+                                                      
		  |2|-----|3|                                                   
		  +-+ (4) +-+                                                                                                   
		 */               

		WUGraph g1 = new WUGraph(), g2 = new WUGraph();	// Initialize graphs.
		g1.addVertex(1);
		g1.addVertex(2);
		g1.addVertex(3);
		g1.addVertex(4);
		g1.addVertex(5);
		g1.addEdge(1, 2, 1);
		g1.addEdge(1, 3, 2);
		g1.addEdge(1, 4, 3);
		g1.addEdge(1, 5, 3);
		g1.addEdge(2, 3, 4);
		g1.addEdge(4, 5, 5);

		System.out.println("\n== Testing initializeVertices() ==\tTotal Tests: 9");
		initializeVertices(g2, g1);	// g2 is new graph (to be minimum span tree), g1 is original.
		for (int i = 1; i <= 5; i++) {
			t = g2.isVertex(i);	// Returns true if in graph g2, false otherwise.
			verify(t, "Vertex " + i + " should be in graph g2 but is not.");
		}

		t = !g2.isVertex(0);
		verify(t, "Vertex 0 should NOT be in graph g2 but it is.");

		t = !g2.isVertex(6);
		verify(t, "Vertex 6 should NOT be in graph g2 but it is.");

		t = g2.isVertex(1);
		verify(t, "Vertex 1 SHOULD be in the graph g2, but it isn't.");

		t = g2.isVertex(3);
		verify(t, "Vertex 3 SHOULD be in the graph g2, but it isn't.");
	}

}
